package com.demo.datastructure.heap;

/**
 * @description: 优先队列类
 * @author: ljr
 * @create: 2022/1/20 11:04 AM
 */
public class MaxPriority<Key extends Comparable<Key>> implements PriorityQueueApi<Key>{

    private Object[] a;

    private int n = 0;

    public MaxPriority(int num){
        a = new Object[num];
    }


    @Override
    public void insert(Key v) {
        if(n == a.length){ return; }
        a[n] = v;
        //向上堆化
        swim(a, n);
        n++;
    }

    private void swim(Object[] a, int n) {
        while (n > 0 && less((Key) a[n],(Key) a[(n-1)/2])){
            exchange(a, n, (n-1)/2);
            n = (n-1)/2;
        }

    }

    private void exchange(Object[] a, int n, int p) {
        Key value = (Key) a[n];
        a[n] = a[p];
        a[p] = value;
    }


    private boolean less(Key value, Key parent){
       return value.compareTo(parent) == 1;
    }

    @Override
    public Key max() {
        if(a == null || a.length == 0) return null;
        return (Key) a[0];
    }

    @Override
    public Key delMax() {
        if(n == 0){
           return null;
        }
        Key value = (Key) a[0];
        a[0] = a[--n];
        a[n] = null;

        //向下堆化
        sink(a, 0, n-1);
        return value;
    }

    private void sink(Object[] a, int i, int n) {
        while(true){
            int max = i;
            if((i * 2 + 1) <= n && less((Key) a[i * 2 + 1], (Key) a[i])) max = i * 2 + 1;
            if((i * 2 + 2) <= n && less((Key) a[i * 2 + 2], (Key) a[max])) max = i * 2 + 2;
            if(max == i) break;
            exchange(a, max, i);
            i = max;
        }
    }


    /**
     * 构建堆
     */
    public void buildHeap(Object[] a){
        if(a == null || a.length == 0) return;
        int i = (a.length - 1) / 2;
        for(; i >= 0; i--){
            sink(a, i,  a.length - 1);
        }
    }

    @Override
    public boolean isEmpty() {
        return n == 0;
    }

    @Override
    public int size() {
        return n;
    }

    public static void main(String[] args) {
        Integer[] nums = new Integer[5];
        nums[0] = 5;
        nums[1] = 1;
        nums[2] = 3;
        nums[3] = 8;
        nums[4] = 6;
        MaxPriority maxPriority = new MaxPriority(5);
        maxPriority.buildHeap(nums);
        System.out.println(maxPriority.max());
    }
}
